Avtor: Helena Angelski
DIRI, Študijsko leto 2004/05
Viri:
Dvojno vrsto smo implementirali kot tabelo, v kateri hranimo cela števila. Pomembno je, da je vrsta predstavljena kot krožna tabela, ki nam omogoča na koncu in začetku vrste dostop do elementov po modulu velikosti tabele. V vrsti lahko hranimo en element manj kot je njena velikost, zato da lahko zaradi krožnega delovanja metod ločimo med polno in prazno vrsto.
V opisu predstavitve vrste s tabelo je že nakazana časovna zahtevnost operacij dvojne vrste. Pri operacijah težimo k temu, da bi bilo izvajanje operacij konstantno, neodvisno od števila elementov v tabeli, se pravi O(1) in ne O(n).
S krožno predstavitvijo vrste dosežemo, da pri brisanju elementov z začetka vrste (operacija odstraniZacetek), ni potrebno elemente prestavljati za eno mesto nazaj (tu bi bila časovna odvisnost izvajanja operacije odvisna od št. elementov), da bi zapolnili manjkajoči prostor. Kar prestavimo, je le indeks, ki kaže na eno mesto pred začetkom vrste. Prestavljanje tega indeksa pa je neodvisno od števila elementov v tabeli in na tak nacin je časovna odvisnost izvajanja operacije konstantna.
Podobno je z operacijo vstaviZacetek – namesto prestavljanja vseh elementov za enega naprej, da bi dobili prosto mesto na začetku, samo prestavimo prej omenjeni indeks, da kaže na eno mesto nazaj. Izvajanje operacije je zopet konstantno.
Pri ostalih operacijah - vstaviKonec, odstraniKonec, konec, zacetek, velikost se ta problem prestavljanja elementov ne pojavlja - element enostavno odstranimo, pobrišemo oz. vrnemo; samo spreminjamo vrednost indeksov, ki označujeta konec in eno mesto pred začetkom vrste, s katerima tudi ves čas operiramo. Te operacije so tako zopet neodvisne od št. elementov v tabeli.
Edina operacija, ki pa je odvisna od št. elementov v tabeli, je operacija toString, kjer pa to drugače ne gre - vsak element pač moramo izpisati posebej, tako da smo odvisni od št. elementov v tabeli.
Je prav tako konstantna, saj poleg dveh spremenljivk, kjer hranimo velikost tabele in seveda samo tabelo, za vsako vrsto potrebujemo prostor le še za dve dodatni spremenljivki - indeks konca in indeks zadnjega prostega mesta pred začetkom vrste. Število spremenljivk, ki jih potrebujemo za katerokoli vrsto, je tako neodvisno od števila elementov v tabeli.